#include "TestCordalidad.h"
#include <iostream>

#define DEBUG_TC

TestCordalidad::TestCordalidad(Grafo &g, vector<int> &orden, bool cografo)
{
  std::reverse(orden.begin(), orden.end());
  cantNodos = orden.size();
  grafo = g;
  coTest = cografo;

  cout << "Creando orden de nodos..." << endl;
  crearOrdenNodos(orden);

  crearHijosVacio();

  cout << "Creando RNs..." << endl;
  crearRNs();
  mostrarRNs();

  //cout << "Creando chequeador de inclusiones..." << endl;
  crearChequeadorDeInclusiones();


  if(!coTest) {
      cout << "Seteando padres..." << endl;
      setearHijos();
      cout << "Vertice:  Padre " << endl;
      for(int i=0; i<cantNodos;i++){
         cout<< i << ":  " <<  padre(i) <<endl;
      }
      }
  else {
      cout << "Seteando no_padres..." << endl;
      co_setearHijos(orden);
      cout << "Vertice:  No_padre " << endl;
      for(int i=0; i<cantNodos;i++){
         cout<< i << ":  " <<  co_padre(i,orden) <<endl;
      }
  }
}

TestCordalidad::~TestCordalidad(){
  delete[] ordenNodos;
  delete[] rns;
  delete[] chequeadorDeInclusiones;
  delete[] hijos;
}

void TestCordalidad::mostrarRNs(){
  cout << "RNs:" << endl;
  for (unsigned int i = 0; i < cantNodos ; i++){
    cout << i << ": ";
  	for (list<int>::iterator it = rns[i].begin(); it != rns[i].end(); it++){
  	  cout << *it << " ";
  	}
  	cout << endl;
  }
}

void TestCordalidad::crearOrdenNodos(vector<int> &orden)
{
  ordenNodos = new int[cantNodos];
  vector<int>::iterator it = orden.begin();
  for(unsigned int i = 0; i < orden.size(); i++, it++)
  {
    ordenNodos[*it] = i;
  }
}

void TestCordalidad::crearHijosVacio()
{
    hijos = new list<int>[cantNodos];
    for(unsigned int i = 0; i < cantNodos; i++)
    {
      hijos[i] = list<int>();
    }
}

void TestCordalidad::setearHijos(){
  for(unsigned int i = 0; i < cantNodos; i++){
    int padreNodoActual = padre(i);
    if (padreNodoActual < (int) cantNodos)
      hijos[padreNodoActual].push_back(i);
  }
}

void TestCordalidad::co_setearHijos(vector<int> &orden){
  for(unsigned int i = 0; i < cantNodos; i++){
   //cout << "Llamando a co_padre con orden: "<< ordenNodos[i]<< " y nodo: " << i  <<endl;
    int noPadreNodoActual = co_padre(i, orden);
   // cout << "noPadreNodoActual " << noPadreNodoActual <<endl;
   // cout << "NodoActual " <<  i <<endl;
    if (noPadreNodoActual < (int) cantNodos)
      hijos[noPadreNodoActual].push_back(i);
  }
}

int TestCordalidad::padre(int nodo){
  list<int> rn = rns[nodo];
  int ordenNodo = ordenNodos[nodo];
  int resultado = cantNodos;
  for(list<int>::iterator it = rn.begin(); it != rn.end(); it++){
    int ordenVecino = ordenNodos[*it];
    if (resultado < (int) cantNodos)
    {
      if(ordenVecino > ordenNodo and ordenVecino < ordenNodos[resultado])
        resultado = *it;
    }
    else
    {
      resultado = *it;
    }
  }
  return resultado;
}

int TestCordalidad::co_padre(int nodo, vector<int> &orden){
  //se requiere el no-vecino mas a la izquierda en el orden de eliminacion
  //uso el chequeador de inclusiones como auxiliar
  if(nodo==(int) (cantNodos-1)){return cantNodos;}
  list<int> rn = rns[nodo];

  //no quiero que el nodo pueda ser padre de si mismo
  //chequeadorDeInclusiones[nodo]=true;
//cout << "nodo " << nodo << endl;
//cout << "ACTIVANDO" <<endl;
  for(list<int>::iterator it = rn.begin(); it != rn.end(); it++){
   // cout << "cheqIncl = true para: " << *it <<endl;
    chequeadorDeInclusiones[*it]=true;
  }

  int no_padre = cantNodos;
   int ordenNodo = ordenNodos[nodo];



/*
cout << "ordenNodo " << ordenNodo << endl;
cout << "ordenNodo + 1: " << ordenNodo + 1 << endl;

cout << "orden : [ " ;
for(vector<int>::iterator it = orden.begin(); it != orden.end(); it++)
{
 cout << *it << " " ;
}
cout << "]" <<endl;
cout << "orden[ordenNodo] " << orden[ordenNodo] << endl;
cout << "orden[ordenNodo + 1] " << orden[ordenNodo + 1] << endl;
*/


//cout << "DESACTIVANDO" <<endl;
  for(int i = ordenNodo + 1; i < (int)cantNodos; i++ ){
     if(chequeadorDeInclusiones[orden[i]]==false)
    {no_padre = orden[i];
     break;
    }
  }


  for(list<int>::iterator it = rn.begin(); it != rn.end(); it++){
   //    cout << "cheqIncl = false para: " << *it <<endl;
    chequeadorDeInclusiones[*it]=false;
  }


  return no_padre;
}

void TestCordalidad::crearRNs(){
  rns = new list<int>[cantNodos];
  for(unsigned int nodo = 0; nodo < cantNodos; nodo++){
    rns[nodo] = crearRN(nodo);
  }
}

list<int> TestCordalidad::crearRN(int nodo){
  list<int> resultado;
  vector<int> vecinos = grafo.adyacencias(nodo);
  for(unsigned int i = 0; i < vecinos.size(); i++){
    int vecino = vecinos[i];
    if(ordenNodos[vecino] > ordenNodos[nodo]){
      resultado.push_back(vecino);
    }
  }
  return resultado;
}

void TestCordalidad::crearChequeadorDeInclusiones(){
  chequeadorDeInclusiones = new bool[cantNodos];
  for(unsigned int i = 0; i < cantNodos; i++){
    chequeadorDeInclusiones[i] = false;
  }
}

bool TestCordalidad::test(){
  bool resultado = true;
  unsigned int padre = 0;
  while(resultado and padre < cantNodos){
   // cout << "Chequeando padre: " << padre << endl;
    if (tieneHijos(padre)){
      resultado = chequearInclusiones(padre);
    }
    //cout << boolalpha << resultado <<endl;
    padre++;
  }
  return resultado;
}

bool TestCordalidad::tieneHijos(int padre)
{
  return hijos[padre].size() > 0;
}

bool TestCordalidad::chequearInclusiones(int padre)
{
  list<int> rnPadre = rns[padre];
  //cout << "Prendiendo..." << endl;
  cambiarChequeadorDeVecinos(rnPadre); //Prendo

  bool resultado = chequearInclusionesDeTodosLosHijos(padre);

  //cout << "Apagando..." << endl;
  cambiarChequeadorDeVecinos(rnPadre); //Apago

  return resultado;

}

bool TestCordalidad::chequearInclusionesDeTodosLosHijos(int padre)
{
  bool resultado = true;
  list<int> todosLosHijos = hijos[padre];
  list<int>::iterator ith = todosLosHijos.begin();
  while (resultado and ith != todosLosHijos.end())
  {
    //cout << "Hijo: " << *ith << endl;
    //cout << "Hijo: " << *ith << " vs Padre: " << padre << endl;
    resultado = chequearIncluidos(padre, rns[*ith]);
   // cout << "resultado: " << boolalpha << resultado << endl;
  	ith++;
  }
  return resultado;
}

void TestCordalidad::cambiarChequeadorDeVecinos(list<int> &nodos){
  for(list<int>::iterator it = nodos.begin(); it != nodos.end(); it++)
    chequeadorDeInclusiones[*it] = not chequeadorDeInclusiones[*it];
}

bool TestCordalidad::chequearIncluidos(int padre, list<int> rn){
  //cout << " chequearIncluidos " << endl;
  //cout << "padre :" << padre << endl;

/*
  cout << "rn :" << endl;
  for (list<int>::iterator it = rn.begin(); it != rn.end();
        it++)
  {
        cout << *it << " ";
  }
  cout << endl;

  cout << "rn padre :" << endl;
  for (list<int>::iterator it = rns[padre].begin(); it != rns[padre].end();
        it++)
  {
        cout << *it << " ";
  }
  cout << endl;
*/


  // La vecinidad no puede exceder en m'as de 1 a la del padre.

  bool resultado = true;
  if(!coTest){
      if(rn.size() > (rns[padre].size() + 1)){return false;}
      list<int>::iterator it = rn.begin();
      while(resultado and it != rn.end()){
        resultado = (*it == padre) or chequeadorDeInclusiones[*it];
        it++;
      }
      return resultado;
  }else{

      int tamRNNoPadre = rns[padre].size();
      int chequeados = 0;
      list<int>::iterator it = rn.begin();
      while(it != rn.end()){
        if(chequeadorDeInclusiones[*it]){chequeados++;}
        it++;
      }
      if (chequeados >= tamRNNoPadre){
         // cout << "chequeados " << chequeados << endl;
         // cout << "tamRNNoPadre " << tamRNNoPadre << endl;
          return true;}
      else {return false;}
  }

}

list<int> TestCordalidad::co_padres(vector<int> &orden)
{
 //el orden ya fue invertido porque vino por referencia despues del constr test
 list<int> resultado = list<int>();
 for(int i=0; i < (int)cantNodos; i++){
     resultado.push_back(co_padre(i, orden));

 }

 return resultado;
}

